#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;

/*6245. 找出中枢整数 显示英文描述
通过的用户数3050
尝试过的用户数3118
用户总通过次数3068
用户总提交次数3438
题目难度Easy
给你一个正整数 n ，找出满足下述条件的 中枢整数 x ：

1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。
返回中枢整数 x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。



示例 1：

输入：n = 8
输出：6
解释：6 是中枢整数，因为 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21 。
示例 2：

输入：n = 1
输出：1
解释：1 是中枢整数，因为 1 = 1 。
示例 3：

输入：n = 4
输出：-1
解释：可以证明不存在满足题目要求的整数。*/
int pivotInteger(int n) {
    int mid = n / 2;

    int sum1 = 0;
    int sum2 = 0;

    for (int i = 1; i <= n; ++i) {
        if (i <= mid) {
            sum1 += i;
        }
        if (i >= mid) {
            sum2 += i;
        }
    }

    if (sum2 == sum1) {
        return mid;
    }

    if (sum1 < sum2) {
        //
        while (sum1 < sum2) {
            mid = mid + 1;
            sum1 = sum1 + mid;
            //sum2应该先减去
            sum2 = sum2 - mid + 1;
        }
        if (sum1 == sum2)
            return mid;
        else
            return -1;


    }

    if (sum1 > sum2) {
        while (sum1 > sum2) {
            sum1 = sum1 - mid;
            sum2 = sum2 + mid;
            mid--;
        }
        if (sum1 == sum2)
            return mid;
        else
            return -1;

    }


    return -1;
}


//感觉思维被限制了住了 刷题刷傻逼了一直想前缀树和 dp
// 输入：s = "coaching", t = "coding"
int appendCharacters(string s, string t) {

    int count = 0;
    int i = 0;
    int j = 0;
    while (i < s.size() && j < t.size()) {
        if (s[i] == t[j]) {
            i++;
            j++;
        } else {
            i++;
        }

    }

    return t.size() - count;

}